/**
 * 
 */
package tree.passed;

/**
 * @author xyyi
 *
 */
public class ConvertSortedListToBinarySearchTree {

	/**
	 * Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST.
	 */
	public TreeNode sortedListToBST(ListNode head) {
		if (head == null)
			return null;
		return sortedListToBST(head, null);
	}

	public TreeNode sortedListToBST(ListNode head, ListNode tail) {
		if (head == tail)
			return null;

		ListNode fast = head;
		ListNode slow = head;
		while (fast.next != tail && fast.next.next != tail) {
			fast = fast.next.next;
			slow = slow.next;
		}

		TreeNode node = new TreeNode(slow.val);
		node.left = sortedListToBST(head, slow);
		node.right = sortedListToBST(slow.next, tail);

		return node;
	}

	/**
	 * Definition for singly-linked list.
	 */
	public class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	/**
	 * Definition for binary tree
	 */
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}

	/**
	 * 
	 */
	public ConvertSortedListToBinarySearchTree() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
